
/**
 * A super ugly number is a positive integer whose prime factors are in the array
 * primes.
 * <p>
 * Given an integer n and an array of integers primes, return the nᵗʰ super ugly
 * number.
 * <p>
 * The nᵗʰ super ugly number is guaranteed to fit in a 32-bit signed integer.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input: n = 12, primes = [2,7,13,19]
 * Output: 32
 * Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12
 * super ugly numbers given primes = [2,7,13,19].
 * <p>
 * <p>
 * Example 2:
 * <p>
 * <p>
 * Input: n = 1, primes = [2,3,5]
 * Output: 1
 * Explanation: 1 has no prime factors, therefore all of its prime factors are in
 * the array primes = [2,3,5].
 * <p>
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= n <= 10⁵
 * 1 <= primes.length <= 100
 * 2 <= primes[i] <= 1000
 * primes[i] is guaranteed to be a prime number.
 * All the values of primes are unique and sorted in ascending order.
 * <p>
 * <p>
 * Related Topics 数组 数学 动态规划 👍 348 👎 0
 */


package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00313SuperUglyNumber {
    public static void main(String[] args) {
        Solution solution = new ID00313SuperUglyNumber().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {

            int[] dp = new int[n + 1];
            int m = primes.length;
            int[] pointer = new int[m];
            for (int a = 0; a < m; a++) {
                pointer[a] = 1;
            }

            dp[1] = 1;

            for (int i = 2; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < m; j++) {
                    int res = dp[pointer[j]] * primes[j];
                    if (res < 0) continue; //越界了
                    min = Math.min(min, res);
                }
                dp[i] = min;
                for (int j = 0; j < m; j++) {
                    int res = dp[pointer[j]] * primes[j];
                    if (res < 0) continue; //越界了
                    if (min == res) {
                        pointer[j]++;
                    }
                }
            }


            return dp[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}